//
//  145. 二叉树的后序遍历.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/27.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution145 {
    // 第一遍练习
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var array: [Int] = []
        postorderT(root, array: &array)
        return array
    }
    func postorderT(_ root: TreeNode?, array: inout [Int]) {
        if root == nil {
            return
        }
        postorderT(root?.left, array: &array)
        postorderT(root?.right, array: &array)
        array.append(root!.val)
    }
    
    // 二叉树的后序遍历，采用迭代法
    func postorderTraversal2(_ root: TreeNode?) -> [Int] {
        var stack: [TreeNode] = []
        var result: [Int] = []
        var cur = root
        var pre: TreeNode?
        while cur != nil || !stack.isEmpty {
            // 不断的将左节点加入栈
            while cur != nil {
                stack.append(cur!)
                cur = cur?.left
            }
            // 弹出栈
            cur = stack.removeLast()
            
            if cur?.right == nil {
                result.append(cur!.val)
                pre = cur
                cur = nil
            } else if cur?.right === pre {
                result.append(cur!.val)
                pre = cur
                cur = nil
            } else {
                stack.append(cur!)
                cur = cur?.right
            }
        }
        return result
    }
    
    static func test() {
        let node1 = TreeNode(1)
        let node2 = TreeNode(2)
        let node3 = TreeNode(3)
        let node4 = TreeNode(4)
        let node5 = TreeNode(5)
        let node6 = TreeNode(6)
        let node7 = TreeNode(7)
        let node9 = TreeNode(9)
        let node10 = TreeNode(10)
        
        node1.left = node2
        node2.left = node4
        node2.right = node5
        node5.left = node9
        node1.right = node3
        node3.left = node6
        node3.right = node7
        node6.right = node10
        
        let result = Solution145().postorderTraversal2(node1)
        print(result)
    }
}
